00100	pUP6 Paper   			First Draft
00200	
00300	1. OUTLINE
00400		Outline
00500		Abstract
00600		Introduction
00700		Ideas
00800		Implementation
00900		Targets
01000		Performance
01100		Conclusions
01200	
01300	2. ABSTRACT
01400	A system has been implemented which can synthesize large inductive inference
01500	programs from restricted English dialogues.  All knowledge and all
01600	control resides in highly structured pieces of code called BEINGS. Each
01700	being has a similar structure, and may therefore be viewed as an extension
01800	of the concept of ACTORS [Hewitt, 1973].  The output code of the system is
01900	also in the form of beings, hence the synthesized program can answer
02000	questions about itself as it runs.   A general description of the
02100	system which realized these ideas is provided, and its target domain is
02200	discussed.  Some unexpected problems, and some unexpected rewards, were
02300	encountered.  Various measures of performance of Automatic Programming 
02400	Systems are proposed, and we compare the current system to previous ones.
02500	We conclude by pooling our ideas into a "view" of Automatic Programming,
02600	and mention future plans.
02700	
02800	2. INTRODUCTION
02900		In this paper we report on a Program-Understanding Program (pUP6)
03000	capable of generating large LISP programs. The methods employed are not
03100	formal, but rather involve structuring of knowledge about programming, about
03200	the task domain, and about transfer of control.  To date, pUP6 has
03300	synthesized three significantly different large (30-page) target programs:
03400	a Winston-like concept formation program [Winston,     ], a grammatical
03500	inference program, and an airline reservation system.  Extended dialogs
03600	are carried on with the user, in a small subset of English, in which the
03700	task is delineated and questionable details are discussed.  Although the
03800	details of these (dialogues and final programs) are the chief concern of
03900	the user, we assume that the reader is interested in studying the ideas
04000	pUP6 embodies, and how they are implemented.  So our treatment will follow
04100	these lines: First, the ideas are presented, including a discussion of
04200	BEINGS.  Next we describe the implementation, and explain our choice of
04300	targets. Only then will we mention performance. Finally, we relate this
04400	work to the field of Automatic Programming.
04500	
04600	3. IDEAS
04700		First, we resolve the uniformity vs. structure controversy.  The
04800	benefits of the former include easy addition of knowledge [Newell, l973]
04900	and simple methods for combining information [McCarthy,    ].  Structure,
05000	however, is necessary for efficient handling of large amounts of data. In
05100	pUP6, we integrate these two ideas into the concept of Beings.  A being is
05200	a collection of about thirty little bits of LISP code; the answers to thirty
05300	questions about the being. That is, we view a small program as equivalent
05400	to its answers to these fixed questions. Every scrap of knowledge, every bit of
05500	control structure should be encoded into beings. There is nothing else in
05600	the system but this interacting community.  Notice that while each being is
05700	highly structured, this structure is uniform over the entire community. Each
05800	being part is itself a little being, etc., and we stop this infinite regress
05900	when the contents of the being part becomes meaninglessly primitive. Each
06000	being is cognizant of the set of thirty questions, and in answering one of
06100	them it may freely ask quesions of other beings (often through nondetermi-
06200	nistic goal statements.)  The reader may glance below at the particular set
06300	of questions used, but we shall discuss our other ideas next.
06400		Since only beings exist, all our code must be written as beings, and
06500	must be written by beings.  A crucial consequence is that _some_ beings must
06600	write code. Our new idea is that the being who knows about X takes charge of
06700	generating code relating to X. For example, the SORT being can do sorting, and
06800	he can also write specialized sort routines, and he can answer questions about
06900	sorting.  A second consequence is that the output code will have all the
07000	"intelligence" that any being community has: it can write variations of itself,
07100	modify itself according to the user's complaints, and answer questions about
07200	what it is doing as it runs.
07300		In a similar vein, _some_ being(s) must do the translation of the 
07400	users' quasi-English inputs into being-usable form.  We choose to have each
07500	being X recognize English related to X.  Thus translation consists of
07600	querying "who can recognize ..." and waiting for a response. Thus our SORT
07700	being must also recognize and process phrases involving sorting or ordering.
07800		Two more ideas are present, constraints which reflect the author's
07900	philosophy:  one need not feel any reverence toward the anthropomorphic
08000	paradigm of programming (ignore details, catch them by blind debugging.)
08100	As in all programming, decisions continually crop up which the system is 
08200	not able to resolve at the time. We have the system spend a significant
08300	effort deferring the decision as long as possible. When, at last, no
08400	progress can be made without its resolution, if the system is still
08500	unsure, either the user settles the question of else a backtrack point is
08600	reluctantly set up.  The second bit of philosophy is that most of the
08700	carelessness bugs can be eliminated through this deferral and through
08800	very precise record-keeping.  Humans depend on their adaptability to 
08900	compensate for limitations in their brain hardware [see Newell and Simon,
09000	1973] but there is no need for an _automatic_ programming system to do so.
     

00100	8. ACKNOWLEDGEMENTS
00200	
00300		There are, of course, countless ideas embodied in any concrete
00400	project.  Sweeping philosophical assumptions are made simply in trying to
00500	d
00600	Program (pUP6) should include the best parts of all the best old ideas.
00700	W
00800	1973], heterarchy [Reddy, l973], structured programming [Dijkstra, l973],
00900	a
01000	directed invocation of procedural knowledge [Winograd, l972], the paradigm
01100	o
01200	[Green, l974].  Of course this list is incomplete; sophistocated ideas are
01300	captured in the languages themselves: QLISP [Sacerdoti], INTERLISP 
01400	[
01500	store, one may acheive new heights merely by synergy.
01600		The success of the BEINGS project, as well as the precursor PUP
01700	programs [Green et al., 1974] is due in large measure to the encouragement,
01800	advice, support, and creative enrgy of C. Cordell Green.  I have also drawn
01900	upon discussions with the SAIL Auotmatic Programming Group, and in par-
02000	ticular with R. Waldinger, D. Barstow, B. McCune, D. Shaw, and L. Steinberg.